/*
 * $Id: LinkedList.hpp 145 2011-11-01 08:52:39Z hyunghwan.chung $
 *
   Copyright 2005-2009 Chung, Hyung-Hwan.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an  BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

#ifndef _XP_BAS_LINKEDLIST_CLASS_
#define _XP_BAS_LINKEDLIST_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/assert.h>
#include <xp/bas/Link.hpp>
#include <xp/bas/MemoryPool.hpp>
#include <xp/bas/MemoryPoolable.hpp>

/*
 * CLASS: xp::bas::LinkedList<T>
 *   A template class for double-linked list
 */
XP_BEGIN_NAMESPACE2 (xp, bas)

template <typename T> class LinkedList;
template <typename T> class SortedLinkedList;

template <typename T> 
class LinkedListNode: protected DoubleLink, protected MemoryPoolable
{
public:
	friend class LinkedList<T>;
	friend class SortedLinkedList<T>;

	T value;

	LinkedListNode<T>* forward () 
	{
		return (LinkedListNode<T>*)link;
	}
	const LinkedListNode<T>* forward () const
	{
		return (const LinkedListNode<T>*)link;
	}

	LinkedListNode<T>* backward ()
	{
		return (LinkedListNode<T>*)back.link;
	}
	const LinkedListNode<T>* backward () const
	{
		return (const LinkedListNode<T>*)back.link;
	}

protected:
	LinkedListNode () {}
	LinkedListNode (const T& v): value(v) {}

	void set_forward (const LinkedListNode<T>* node)
	{
		link = (Link*)node;
	}
	void set_backward (const LinkedListNode<T>* node)
	{
		back.link = (Link*)node;
	}
};

template <typename T> class LinkedList
{
public:
	typedef LinkedListNode<T> Node;

	enum 
	{
		INVALID_INDEX = ~(xp_size_t)0
	};

	~LinkedList () 
	{
		clearout ();
	}

	LinkedList (xp_size_t mpb_size = 0): mp (xp_sizeof(Node), mpb_size)
	{
		this->node_count = 0;
		this->head_node = XP_NULL;
		this->tail_node = XP_NULL;
	}

	LinkedList (const LinkedList<T>& ll): mp (ll.mp.datumSize(), ll.mp.blockSize())
	{
		this->node_count = 0;
		this->head_node = XP_NULL;
		this->tail_node = XP_NULL;
		for (Node* p = ll.head_node; p != XP_NULL; p = p->forward()) 
			append (p->value);
	}

	LinkedList<T>& operator= (const LinkedList<T>& ll) 
	{
		if (this != &ll)
		{
			this->clear ();
			for (Node* p = ll.head_node; p != XP_NULL; p = p->forward())
				this->append (p->value);
		}
		return *this;
	}
	
	T& operator[] (xp_size_t index)
	{
		xp_assert (index < size());
		
		Node* p = head_node;
		while (index > 0) 
		{
		    p = p->forward();
		    index--;
		}
		xp_assert (p != XP_NULL);
		return p->value;
	}

	const T& operator[] (xp_size_t index) const
	{
		xp_assert (index < size());
		
		Node* p = head_node;
		while (index > 0) {
		    p = p->forward();
		    index--;
		}
		xp_assert (p != XP_NULL);
		return p->value;
	}

	MemoryPool& getMemoryPool ()
	{
		return this->mp;
	}

	xp_size_t mpBlockSize() const
	{
		return this->mp.blockSize();
	}

	bool mpIsEnabled () const
	{
		return this->mp.isEnabled();
	}

	xp_size_t size () const 
	{
		return node_count;
	}

	int isEmpty () const 
	{
		return node_count == 0;
	}

	bool contains (const T& value) const
	{
		return nodeOf(value) != XP_NULL;    
	}

	// insert an externally created node.
	// may need to take extra care when using this method.
	Node* insertNode (Node* pos, Node* node);

	// create a new node to hold the value and insert it.
	Node* insertValue (Node* pos, const T& value)
	{
		Node* n = mp.isEnabled()? 
			(new(&mp) Node(value)): (new Node(value));
		return insertNode (pos, n);
	}

	T& insert (Node* node, const T& value)
	{
		return insertValue (node, value)->value;
	}

	T& insert (xp_size_t index, const T& value)
	{
		xp_assert (index <= node_count);

		if (index == node_count) return insert ((Node*)XP_NULL, value);

		register Node* np;
		register xp_size_t cnt;
		if (index < (node_count >> 1)) {
			for (np = head_node, cnt = 0;
			     cnt < index; np = np->forward(), cnt++) {
				xp_assert (np != XP_NULL);
			}
		}
		else {
			for (np = tail_node, cnt = node_count - 1;
			     cnt > index; np = np->backward(), cnt--) {
				xp_assert (np != XP_NULL);
			}
		}
		return insert (np, value);
	}

	T& prepend (const T& value)
	{
		return insert (head_node, value);
	}
	T& append (const T& value)
	{
		return insert ((Node*)XP_NULL, value);
	}

	Node* prependNode (Node* node)
	{
		return insertNode (head_node, node);
	}
	Node* appendNode (Node* node)
	{
		return insertNode ((Node*)XP_NULL, node);
	}

	Node* prependValue (const T& value)
	{
		return insertValue (head_node, value);
	}
	Node* appendValue (const T& value)
	{
		return insertValue ((Node*)XP_NULL, value);
	}

	void prependAll (const LinkedList<T>& list)
	{
		Node* n = list.tail_node;

		if (&list == this) {
			Node* head = list.head_node;
			while (n) {
				prepend (n->value);
				if (n == head) break;
				n = (Node*)n->back.link;
			}
		}
		else {
			while (n) {
				prepend (n->value);
				n = (Node*)n->back.link;
			}
		}
	}

	void appendAll (const LinkedList<T>& list) 
	{
		Node* n = list.head_node;

		if (&list == this)  {
			Node* tail = list.tail_node;
			while (n != XP_NULL) {
				append (n->value);
				if (n == tail) break;
				n = n->forward();
			}
		}
		else {
			while (n != XP_NULL) {
				append (n->value);
				n = n->forward();
			}
		}
	}

	// remove a node from the list without freeing it.
	// take extra care when using this method as the node 
	// can be freed through the memory pool when the list is 
	// destructed if the memory pool is enabled.
	Node* yield (Node* node, bool clear_links = true);

	// remove a node from the list and free it.
	void remove (Node* node)
	{
		yield (node, false);
		if (mp.isDisabled()) delete node;
		else 
		{
			node->~Node ();
		#if defined(_MSC_VER)
			node->operator delete (node, &mp);
		#else
			node->dispose (node, &mp);
		#endif
		}
	}

	void remove (xp_size_t index) 
	{
		xp_assert (index < node_count);

		Node* np = head_node; 
		while (index > 0) {
			np = np->forward();
			index--;
		}
		remove (np);
	}

	Node* yieldByValue (const T& value, bool clear_links = true)
	{
		Node* p = nodeOf (value);
		if (p == XP_NULL) return -1;
		return yield (p, clear_links);
	}

	int removeByValue (const T& value)
	{	
		Node* p = nodeOf (value);
		if (p == XP_NULL) return -1;
		remove (p);
		return 0;
	}

	int removeAllByValue (const T& value)
	{
		Node* p = nodeOf(value);
		if (p == XP_NULL) return -1;
		do {
			Node* tmp = p->forward();
			remove (p);
			p = nodeOf (value, tmp);
		} while (p != XP_NULL);
		return 0;
	}

	void removeHead ()
	{
		this->remove (this->head_node);
	}
	void removeTail ()
	{
		this->remove (this->tail_node);
	}

	Node* head () const 
	{
		return (Node*)head_node;
	}
	Node* tail () const 
	{
		return (Node*)tail_node;
	}

	Node* nodeAt (xp_size_t index) const
	{
		xp_assert (index < node_count);
		Node* p = head_node;
		while (index > 0) {
			p = p->forward();
			index--;
		}
		xp_assert (p != XP_NULL);
		return p;
	}

	Node* nodeOf (const T& value) const
	{
		for (Node* p = head_node; p != XP_NULL; p = p->forward()) {
			if (value == p->value) return p;
		}
		return XP_NULL;
	}
	Node* lastNodeOf (const T& value) const
	{
		for (Node* p = tail_node; p != XP_NULL; p = p->backward()) {
			if (value == p->value) return p;
		}
		return XP_NULL;
	}	

	Node* nodeOf (const T& value, Node* head) const
	{
		for (Node* p = head; p != XP_NULL; p = p->forward()) {
			if (value == p->value) return p;
		}
		return XP_NULL;
	}

	Node* lastNodeOf (const T& value, Node* tail) const
	{
		for (Node* p = tail; p != XP_NULL; p = p->backward()) 
		{
			if (value == p->value) return p;
		}
		return XP_NULL;
	}	

	xp_size_t indexOf (const T& value) const
	{
		xp_size_t index = 0;
		for (Node* p = head_node; p != XP_NULL; p = p->forward()) 
		{
			if (value == p->value) return index;
			index++;
		}
		return INVALID_INDEX;
	}
	xp_size_t lastIndexOf (const T& value) const
	{
		xp_size_t index = node_count;
		for (Node* p = tail_node; p != XP_NULL; p = p->backward()) 
		{
			index--;
			if (value == p->value) return index;
		}
		return INVALID_INDEX;
	}

	T& get (xp_size_t index) 
	{
		xp_assert (index < node_count);
		Node* p = head_node;
		while (index > 0) {
			p = p->forward();
			index--;
		}
		xp_assert (p != XP_NULL);
		return p->value;
	}

	const T& get (xp_size_t index) const
	{
		xp_assert (index < node_count);
		Node* p = head_node;
		while (index > 0) {
			p = p->forward();
			index--;
		}
		xp_assert (p != XP_NULL);
		return p->value;
	}

	void set (xp_size_t index, const T& value)
	{
		xp_assert (index < node_count);

		Node* p = head_node;
		while (index > 0) {
			p = p->forward();
			index--;
		}
		xp_assert (p != XP_NULL);
		p->value = value;
	}
	
	void clear () 
	{
		Node* p, * saved;

		p = head_node;
		while (p) 
		{
			saved = p->forward();
			
			if (mp.isDisabled()) delete p;
			else {
				p->~Node ();
			#if defined(_MSC_VER)
				p->operator delete (p, &mp);
			#else
				p->dispose (p, &mp);
			#endif
			}

			node_count--;
			p = saved;
		}

		head_node = tail_node = XP_NULL;
		xp_assert (node_count == 0);
	}

	void clearout ()
	{
		clear ();
		mp.dispose ();
	}

	typedef int (LinkedList<T>::*TraverseCallback) (Node* start, Node* cur);

	void traverse (TraverseCallback callback, Node* start)
	{
		Node* cur, * prev, * next;

		cur = start;
		while (cur != XP_NULL) 
		{
			prev = cur->backward();
			next = cur->forward();

			int n = (this->*callback) (start, cur);

			if (n > 0) cur = next;
			else if (n < 0) cur = prev;
			else break;
		}
	}

protected:
	MemoryPool mp;
	Node*      head_node;
	Node*      tail_node;	
	xp_size_t  node_count;
};

template <typename T> 
inline typename LinkedList<T>::Node* LinkedList<T>::insertNode (
	Node* pos, Node* n)
{
	if (pos == XP_NULL) 
	{
		if (node_count == 0) 
		{
			xp_assert (head_node == XP_NULL);
			xp_assert (tail_node == XP_NULL);
			head_node = tail_node = n;
		}	
		else 
		{
			n->back.link = tail_node;
			tail_node->set_forward(n);
			tail_node = n;
		}
	}
	else 
	{
		n->set_forward(pos);
		n->set_backward(pos->backward());
		if (pos->back.link != XP_NULL)
			pos->backward()->set_forward(n);
		else head_node = n;
		pos->set_backward(n);
	}

	node_count++;
	return n;
}

template <typename T>
inline typename LinkedList<T>::Node* LinkedList<T>::yield (Node* node, bool clear_links) 
{
	xp_assert (node != XP_NULL);
	xp_assert (this->node_count > 0);

	if (node->forward()) 
		node->forward()->set_backward (node->backward());
	else
		this->tail_node = node->backward();

	if (node->backward())
		node->backward()->set_forward (node->forward());
	else
		this->head_node = node->forward();
		
	this->node_count--;

	if (clear_links)
	{
		node->set_forward (XP_NULL);
		node->set_backward (XP_NULL);
	}

	return node;
}

XP_END_NAMESPACE2 (xp, bas)

#endif


